// 实现前缀树数据结构的相关类Tries类

// 思路：实现Trie，字典树或者前缀树，是一个多叉树，每个节点都拥有一个map和isEnd标识是否有该字符串
// 时间复杂度：O(n)，n是字符串的长度
// 空间复杂度：O(n)，map的大小

function Node() {
    this.children = new Map
    this.isEnd = false
}

function Trie() {
    this.root = new Node()
}

Trie.prototype.insert = function (str) {
    let cur = this.root
    for (const char of str) {
        if (!cur.children.has(char)) {
            cur.children.set(char, new Node())
        }
        cur = cur.children.get(char)
    }
    cur.isEnd = true
}

Trie.prototype.search = function (str) {
    let cur = this.root
    for (const char of str) {
        if (!cur.children.has(char)) {
            return false
        }
        cur = cur.children.get(char)
    }
    return cur.isEnd
}

Trie.prototype.startsWith = function (prefix) {
    let cur = this.root
    for (const char of prefix) {
        if (!cur.children.has(char)) {
            return false
        }
        cur = cur.children.get(char)
    }
    return !!cur
}

const trie = new Trie()
console.log(trie.insert('apple'));
console.log(trie.insert('abs'));
console.log(trie.search('apple'))
console.log(trie.startsWith('apple'))